function expand(s, left, right, len = s.length) {
    let [l, r] = [left, right]
    while (l >= 0 && r < len && s.charAt(l) === s.charAt(r)) {
        l--
        r++
    }
    return r - l - 1
}

function getLongPalindrome(str, len = str.length) {
    let start = 0, end = 0
    for (let i = 0; i < len; i++) {
        let odd = expand(str, i, i) // 奇数
        let even = expand(str, i, i + 1) // 偶数
        const max = Math.max(odd, even)
        if (max > end - start) {
            start = i - Math.floor((max - 1) / 2)
            end = i + Math.floor(max / 2)
        }
    }
    return str.substr(start, end)
}

function preProcess(str) {
    if (str.length === 0) { return '^$' }
    let res = '^'
    for (let i = 0; i < str.length; i++) {
        res += '#' + str.charAt(i)
    }
    res += '#$'
    return res
}
function manacher(string) {
    let str = preProcess(string)
    let len = str.length
    let [r, center] = [0, 0]
    const p = new Array(len).fill(0)
    // 去除两端的 ^ 和 $
    for (let j = 1; j < len - 1; j++) {
        let i = 2 * center - j
        if (r > j) {
            p[j] = Math.min(r - j, p[i])
        } else {
            p[j] = 0
        }
        // 重新计算
        while (str.charAt(j - p[j] - 1) === str.charAt(j + p[j] + 1)) {
            p[j]++
        }
        // 更新 r、center
        if (j + p[j] > r) {
            center = j
            r = j + p[j]
        }
    }

    // 找出 p 的最大值
    let maxLen = 0;
    let centerIndex = 0;
    for (let i = 1; i < len - 1; i++) {
        if (p[i] > maxLen) {
            maxLen = p[i];
            centerIndex = i;
        }
    }
    let start = (centerIndex - maxLen) / 2;
    return string.substring(start, start + maxLen);
}

// console.log(getLongPalindrome('abcbcbds'))
console.log(manacher('abcbcbds'))
